1. Field of the Invention
The present invention relates generally to a method for video compression, and more particularly, to a method of selecting a coding mode for intra-predicted block data within an image frame.
2. Background of the Invention
The ITU-T H.264 standard, which is also named MPEG-4 Part-10 Advanced Video Coding (AVC), has recently been developed as a next-generation compression tool for the coding of video content. Experimental results show that the H.264 standard provides a factor of two in compression efficiency compared to other exiting standards. Therefore, the H.264 standard is very suitable for use in the growing applications of Internet streaming, multimedia communications, and mobile televisions.
During the coding of a current block, to remove the spatial redundancy between its neighboring blocks, the H.264 standard provides a coding tool called “intra prediction” to form predictors from pixels around the current coding block. As shown in FIG. 1, according to the H.264 standard, there are a total of nine intra prediction modes for each 4 by 4 Luma block. Furthermore, FIG. 2 shows boundary pixels (A to L, and X) that are used to form the predictors (a to p) of the 4 by 4 predicted block in each of the prediction modes. The residual between the current coding block and the predicted block, which is formed according to a prediction mode, is processed by further coding procedures, such as transformation, quantization, and entropy coding to produce a compressed bitstream. Choosing a suitable intra prediction mode is important for the performance of compression as the more similar a predicted block is to the current coding block, the smaller the resulting residual is. Therefore, the amount of information that needs to be compressed is largely decreased so that the performance of compression can be improved.
A number of technologies for fast-selecting the intra prediction mode and rapidly performing the intra prediction have been introduced in the market. For example, in Japan Patent No. 2004-140473, an image information coding apparatus is provided to rapidly intra-predict each block based on a pipeline process. The apparatus sequentially processes the respective blocks in a pre-determined order except for the raster scanning.
In U.S. patent Publication No. 2003/0206594, a method of encoding intra frame is disclosed, which provides a probability table of the prediction modes according to an expected complexity of an encoder. The probability table is adjustable so that the blocks can be coded in a low-complexity encoding by using the low-complexity subset of modes, or in a high-complexity encoding using any prediction mode. This permits a low-complexity decoder responsive to only the low-complexity subset of modes.
U.S. patent Publication No. 2003/0223645 discloses methods and systems for estimating a pixel prediction mode to be used in a video encoding or decoding process. This application classifies the prediction modes by five groups that are ordered in a manner with their likelihood of producing a reduced prediction error. The prediction mode order is expressed according to the positions of the blocks that are near the edges or boundaries of an image frame.
U.S. patent Publication No. 2004/0008771 discloses a method and device for coding a digital image using an intra-mode block prediction. The modes assigned to each combination of prediction modes may be divided into two groups. The first group includes n most probable prediction modes (where n is smaller than the overall number of available modes) and the second group includes the remaining modes. The modes in the first group are ordered according to their probability. This order may be specified as a list of modes ordered from the most probable mode to the least probable mode. The modes of the second group may be ordered in a predetermined manner, which may be specified depending on the information already available to a decoder.
Furthermore, one known technology selects an intra prediction mode with a reasonable computational complexity via various approaches including a partially computation of the cost function, an early termination, and a selective computation of highly probable modes to save the time of selecting the intra prediction mode. Another known technology provides a fast mode selection method by examining the most probable modes. This method is based on an assumption that the suitable prediction mode of a block is most likely in the direction of a local edge within that block. The local edge information is obtained with additional calculations for the edge feature parameters of the current coding block. For more details on the fast algorithms for intra prediction mode selection, references may be made to B. Meng and O. C. Au, “Fast intra-prediction mode selection by 4 by 4 blocks in H.264,” in Proc. Of 2003 IEEE Int. Conf. On Acoustics, Speech, and Signal Processing (ICASSP '03), April 2003, and Y. D. Zhang, F. Dai, and S. X. Lin, “Fast 4 by 4 Intra-prediction Mode Selection for H.264,” in Proc. Of 2004 IEEE Int. Conf. On Multimedia and Expo (ICME '04), July 2004.
The above technologies, however, only rely on fewer candidates of modes and roughly evaluate matching errors of the predicted blocks. Therefore, there are some difficulties in achieving an optimum selection of intra prediction modes. That is, these prior art methodologies cannot achieve maximum compression performance.
Furthermore, to achieve the best compression performance, each 4 by 4 block in an image frame needs to be encoded with its optimal intra prediction mode. To find the optimal intra prediction mode, a full search (FS) is commonly used for all the nine prediction modes of FIG. 1 because of its good performance and regularity for easy implementation. In an H.264 reference program JM 7.3, a full search algorithm is developed to select the optimal mode for each 4 by 4 block. The cost measure for each mode is based on the sum of absolute difference (SAD) between the predicted block and the current coding block. Let C(i, j) and Pm(i, j) be the pixel intensities at coordinate (i, j) of the current 4 by 4 coding block (C) and the predicted 4 by 4 block (Pm) according to mode m (0≦m≦8), respectively. The sum of absolute difference between Pm and C is denoted by SAD(m), which is given by:SAD(m)=ΣΣ|Pm(i,j)−C(i,j)|, 0≦(i,j)≦3  (1)
Therefore, in the H.264 reference program, the FS method may include the following steps:
(1) Generating a predicted 4 by 4 block Pm according to the mode m;
(2) Calculating the cost of the mode m, denoted by COST(m) as given below:COST(m)=SAD(m)+4*F(QP)*MP  (2)
wherein F(QP) is a function of the quantization parameter (QP) and F(QP)≧0. MP is 0 if m is the most probable mode; otherwise MP is 1.
(3) Repeating steps (1) and (2) for 0≦m≦8. Choosing the one that has the minimum COST(m) as the optimal intra prediction mode.
According to the H.264 reference program, except for the mode (0) (vertical prediction) and mode 1 (horizontal prediction), the predictors in other modes are calculated by the mathematical functions of the boundary pixels. Take the mode 2 (DC prediction) as an example. Each predictor in the DC predicted block has the same value that is calculated from (4A+4B+4C+4D+4I+4J+4K+4L+4)>>3, wherein {A, B, C, D, I, J, K, L} are the boundary pixels as shown in FIG. 2, and >> is a bit-wise operator for a shift-right operation. For a digital signal processor (DSP) with single operation for accumulative multiplication, the count of operations for generating DC predicted block is 9 (i.e., 8 accumulative multiplication and 1 shifting.) The expressions and the counts of operations for other 8 modes are shown in Tables I-IX, which show a total of 192 operations for generating predictors in these 9 modes. (See Table X at the end of the specification.) If fixed QP is used for each block, it takes 31 operations for COST(m) when m is the most probable mode; otherwise 32 operations are needed. As a result, the FS method would take (192+31+32*8)=479 operations for each 4 by 4 blocks. This large operation number is computationally expensive for the FS method.
Therefore, there is a need for a new approach to find the optimal intra prediction mode, which is computationally efficient compared to the FS method.